package com.ruoyi.system.spi;

import java.util.*;

public class Main {


    //输入的第一行包括一个正整数t(1 <= t <= 100), 表示数据组数。
//接下来t行, 每行一组数据。
//每行的第一个整数为整数的个数n(1 <= n <= 100)。
//接下来n个正整数, 即需要求和的每个正整数。


    // 固定一个不变，在体积V下，选或者不选; 在体积V下，前n个物品的最大值  0/1背包，要么选，要么不选。

    //  装满，
    public int test(int v, int[] vs, int[] values) {
        int length = vs.length;
        int[][] dp = new int[v + 1][length];
        for (int i = 0; i < v + 1; i++) {
            for (int j = 0; j < length; j++) {
                // 如果体积小于当前，默认取前一个
                if (j == 0) {
                    // 如果是第一个,并且此时体积比较大
                    if (i > vs[j] && j == vs[i]) {
                        dp[j][i] = values[i];
                    } else {
                        dp[j][i] = Integer.MIN_VALUE; // 由于是最小的值，所以肯定不会选到。
                    }
                    continue;
                }
                //  以前都还没有i，所以选不到。 如何来防止多次选的？  用一个体积，要么选物品，要么不选物品。 在每次的选择的时候，已经做了限制。只能选择已经有的，没有的不能被选择。
                //
                if (j >= values[i]) {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - vs[i]][j - 1] + values[i]);
                    // v 不变 v=[v-1][j]+[v-1][j-1];  要么装i 要么不装i,   在一个体积为4的背包中，装入 前 i个物品的最大值。。  。
                    //  如果体积小，
                } else {
                    // 如果小于体积，所以只能选择前一个，，因为这个没法装入
                    dp[i][j] = dp[i][j - 1];
                }
            }
        }
        return dp[v][vs.length - 1];

    }


    //给定一个长度为 n 的字符串和一个指定行数 k ，请你从上到下，从左到右地把这个字符串转换成 z 字形，一共 n 行。
    //
    //例如输入的字符串是 "nowcoder"，k=3，则转换成的 z 字形是
    //n  o
    //ocdr
    //w e
    //然后返回这个新字符串，noocdrwe
    public static String zconvert(String str, int k) {

        if (k == 1) {
            return str;
        }
        if (k == 2) {
            StringBuilder stringBuilder = new StringBuilder();
            StringBuilder stringBuilder1 = new StringBuilder();
            for (int i = 0; i < str.length(); i += 2) {
                stringBuilder.append(str.charAt(i));
                if (i + 1 < str.length()) {
                    stringBuilder1.append(str.charAt(i + 1));
                }

            }
            return stringBuilder.append(stringBuilder1).toString();
        }
        int n = str.length();
        int recyc = 2 * k - 2;
        // 宽度
        int wid = (n / recyc + 1) * (k - 1);
        Character[][] dp = new Character[k][wid];
        // 向下
        boolean mark = true;
        int i = 0;
        int index = 0;
        for (int j = 0; j < wid; j++) {
            //向下
            if (mark) {
                i = 0;
                for (int l = 0; l < k; l++) {
                    if (index >= n) {
                        break;
                    }
                    dp[i++][j] = str.charAt(index++);
                }
                mark = false;
            } else {
                i = k - 2;
                for (int l = 0; l < k - 2; l++) {
                    if (index >= n) {
                        break;
                    }
                    if (l == k - 3) {
                        dp[i--][j] = str.charAt(index++);
                        continue;
                    }
                    dp[i--][j++] = str.charAt(index++);
                }
                mark = true;
            }
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int l = 0; l < k; l++) {
            for (int j = 0; j < wid; j++) {
                if (dp[l][j] != null) {
                    stringBuilder.append(dp[l][j]);
                }
            }
        }
        return stringBuilder.toString();
    }


    // 采用公式处理
    public static String zconvert1(String str, int k) {

        int length = str.length();
        int recyc = 2 * k - 2;
        if (k == 1) {
            return str;
        }
        if (k == 2) {
            StringBuilder first = new StringBuilder();
            StringBuilder second = new StringBuilder();
            for (int i = 0; i < length; i = i + 2) {
                first.append(str.charAt(i));
                if (i + 1 < length) {
                    second.append(str.charAt(i + 1));
                }
            }
            return first.append(second).toString();
        }
        HashMap<Integer, StringBuilder> integerStringBuilderHashMap = new HashMap<>();
        for (int i = 0; i < recyc; i++) {
            if (i < k) {
                // 小于key,直接新增
                integerStringBuilderHashMap.put(i, new StringBuilder());
            } else {
                // 大于key，从原来的里面获取
                integerStringBuilderHashMap.put(i, integerStringBuilderHashMap.get(2 * k - 2 - i));
            }
        }
        for (int i = 0; i < length; i++) {
            integerStringBuilderHashMap.get(i % recyc).append(str.charAt(i));
        }
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < k; i++) {
            stringBuilder.append(integerStringBuilderHashMap.get(i));
        }
        return stringBuilder.toString();
    }


    public static int minMoves(int target, int maxDoubles) {
        int n = 0;
        int temp = maxDoubles;
        if (target == 1) {
            return 0;
        }
        while (target > 1) {
            if (target % 2 == 0 && maxDoubles > 0) {
                //偶数，直接去一半
                target = target / 2;
                maxDoubles--;
            } else {
                target = target - 1;
                ++n;
                if (maxDoubles == 0) {
                    n += (target - 1);
                    target = 1;
                }
            }
        }
        n += (temp - maxDoubles);
        return n;
    }

    //10 /2= 5    5-1 = 4    2  2/2=1
    public static void main(String[] args) {
        String nowcoder = zconvert1("lrbbmqbh", 2);
        System.out.println(nowcoder);


        //lbmbrbqh

    }


    public int getsmall(int[] forbidden, int a, int b, int x) {

        ArrayDeque<Integer> quenu = new ArrayDeque<>();
        int length = forbidden.length;
        int begin = 0;

        for (int i = 0; i < length; i++) {

            if (begin != forbidden[length]) {

                break;
            } else {

            }

        }
        // 先不考虑禁止地带
        HashMap<Integer, Integer> value = new HashMap<>();
        quenu.add(0);
        value.put(0, 0);
        while (!quenu.isEmpty()) {
            Integer pop = quenu.pop();
            // 弹出来，放进去
            // 已经到位了
            if (pop == x) {

                //  你需要淡定，淡定，再淡定。 平静的心

                break;

            }

        }

        return 0;
    }


    public int getsmall1(int[] forbidden, int a, int b, int x) {

        HashMap<Integer, Integer> temp = new HashMap<>();

        recyc(forbidden, a, b, 0, 0, 0, temp, x);

        return 0;
    }

    public int recyc(int[] forbidden, int a, int b, int x, int n, int mark, HashMap<Integer, Integer> temp, int target) {

        for (int i = 0; i < forbidden.length; i++) {
            if (x == forbidden[i]) {
                return -1;
            }
        }
        // 正常判断
        if (x == target) {

       // temp.put(temp)

        }
        int min = Math.min(recyc(forbidden, a, b, x + a, n + 1, mark, temp, target), recyc(forbidden, a, b, x - b, n + 1, mark, temp, target));

        return min;
    }


}
